Bem-vindo à Aula 3 de Conceitos de Inteligência Artificial (PolyU COMP5511). Nesta sessão, fazemos a transição da busca de caminho de agente único para Busca Adversarial, onde os agentes operam em ambientes multiagente competitivos. Também introduzimos Problemas de Satisfação de Restrições (CSPs), um paradigma onde o objetivo é encontrar um estado que satisfaça um conjunto específico de restrições, em vez de um caminho.
Conceitos Centrais
- Busca Adversarial: Foca em algoritmos como Minimax e Poda Alpha-Beta para tomar decisões racionais contra um oponente inteligente.
- Busca em Árvore Monte Carlo (MCTS): Explora a tomada de decisão probabilística, servindo como a base para IAs de jogos modernas como AlphaGo.
- Satisfação de Restrições: Modela problemas usando Variáveis, Domínios e Restrições, resolvidos via Backtracking e Busca Local.
Análise de Complexidade
Em cenários adversariais, a complexidade do espaço de busca é frequentemente definida pelo fator de ramificação do jogo
Aviso de Mudança de Paradigma
Ao contrário da busca padrão (por exemplo, A* ou BFS), onde o ambiente é estático, Busca Adversarial assume que o ambiente (o oponente) tenta ativamente minimizar seu sucesso. Em CSPs, a ordem das ações importa menos do que a validade da atribuição final.
Pseudocódigo Conceitual: Tipos de Agente
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).